Задача про кістякове дерево екстремальної ваги

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра СКС

Інформація про роботу

Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика

Частина тексту файла

Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра СКС / Звіт з лабораторної роботи № 2 з дисципліни: “Дискретна математика” на тему: “Задача про кістякове дерево екстремальної ваги” Теоретичні відомості При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі. Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає. Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда). Крок 1. Присвоєння початкових значень. S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером). S''= S\S', V' = Ø Крок 2. Оновлення даних. Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''} Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)} Крок 3. Перевірка на завершення. Якщо S' = S, то G' = (S', V') - шуканий граф. В іншому випадку переходимо на Крок 2. Далі наведено приклад виконання алгоритму Пріма. Граф задано списком ребер з вказанням їх ваг. (1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5), (4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2). Відповідний цьому списку граф / Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування. (1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5). Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги). S = {1,2,3,4,5} Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)} S' = {1,4} S'' = {2,3,5} Крок 3. S'≠S Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)} Крок 3. S'≠S Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)} S' = {1,2,4,5} S'' = {3} Крок 3. S'≠S Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)} S' = {1,2,3,4,5} S'' = Ø Крок 3. S'=S Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа. / Вага отриманого кістякового дерева дорівнює 10. Індивідуальне завдання Знайти мінімальну вагу кістякового дерева. Результат виконання програми /
Антиботан аватар за замовчуванням

27.03.2016 18:03

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини